package org.molamil.acto.core.parsers {

	/**
	 * Class that represents a list of <code>Prioritizable</code> objects, offering
	 * basic collection-type methods.
	 * 
	 * @author Jorge Hernandez
	 * @see org.molamil.core.parsers.Prioritizable
	 */
	public class PrioritizableList {
		
		
		// PROPERTIES
		
		protected var _a:Array;
		
		
		// CONSTRUCTOR
		
		/**
		 * Initializes the implicit array.
		 */
		public function PrioritizableList() {
			_a = new Array();
		}
		
		
		// PUBLIC METHODS
		
		/**
		 * Adds one <code>Prioritizable</code> object to the list.
		 * 
		 * <p>Note that the item will not be added if it is already in the list or if
		 * the item is null.</p>
		 * 
		 * @param item
		 */
		public function add(item:Prioritizable):void {
			if (!contains(item) && item != null)
				_a.push(item);
		}
		
		/**
		 * Removes the passed item from the list, if the list contains this item.
		 * 
		 * @param item
		 */
		public function remove(item:Prioritizable):void {
			var i:int = _a.indexOf(item);
			if (i != -1)
				_a.splice(i, 1);
		}
		
		/**
		 * @param item
		 * @return Whether the list contains that item
		 */
		public function contains(item:Prioritizable):Boolean {
			return _a.indexOf(item) != -1;
		}
		
		/**
		 * Sorts the list based on <code>Prioritizable.getPriority()</code>, lower priorities come first.  
		 */
		public function sort():void {
			quicksort(0, _a.length);
		}

		/**
		 * Removes all elements from the list.
		 */
		public function clear():void {
			_a = new Array();
		}
		
		
		// PRIVATE METHODS
			
		private function quicksort(lo:int, hi:int):void {
			if (hi - lo <= 1)
				return;
			var pivot:Prioritizable = _a[hi - 1];
			var split:int = lo;
			for (var i:int = lo; i < hi - 1; i++) {
				if (Prioritizable(_a[i]).priority < pivot.priority) {
					var tmp:Prioritizable = _a[i];
					_a[i] = _a[split];
					_a[split] = tmp;
					split++;
				}
			}
			var tmpBis:Prioritizable = _a[hi - 1];
			_a[hi - 1] = _a[split];
			_a[split] = tmpBis;
			quicksort(lo, split);
			quicksort(split + 1, hi);
			return;
		}
		
		
		// GETTER/SETTER
		
		/**
		 * @return The underlying array used to hold the list items
		 */
		public function get a():Array {
			return _a;
		}
		
		
	}
	
}
